package com.graph6;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class GroupTest2 {

	/**
	 * <code>
	 * 	LIBRARY          LIBRARY DEPENDENCIES
	=======          ====================
	des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
	dw01             ieee dw01 dware gtech
	dw02             ieee dw02 dware
	dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
	dw04             dw04 ieee dw01 dware gtech
	dw05             dw05 ieee dware
	dw06             dw06 ieee dware
	dw07             ieee dware
	dware            ieee dware
	gtech            ieee gtech
	ramlib           std ieee
	std_cell_lib     ieee std_cell_lib
	synopsys
	 * </code>
	 * 
	 */

	public static void main(String[] args) {
//    	              0   1      2              3     4      5     6    7
//		String s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05, "
//        		    8     9     10      11    12        13           14
//				+ "dw06, dw07, dware, gtech, ramlib, std_cell_lib, synopsys";
		int[][] edges = new int[][] { //
				{ 2, 0 }, { 2, 14 }, { 2, 13 }, { 2, 4 }, { 2, 3 }, { 2, 12 }, { 2, 1 }, //
				{ 3, 1 }, { 3, 10 }, { 3, 11 }, //
				{ 4, 1 }, { 4, 10 }, //
				{ 5, 0 }, { 5, 14 }, { 5, 10 }, { 5, 4 }, { 5, 3 }, { 5, 1 }, { 5, 11 }, //
				{ 6, 1 }, { 6, 3 }, { 6, 10 }, { 6, 11 }, //
				{ 7, 1 }, { 7, 10 }, //
				{ 8, 1 }, { 8, 10 }, //
				{ 9, 1 }, { 9, 10 }, //
				{ 10, 1 }, //
				{ 11, 1 }, //
				{ 12, 0 }, { 12, 1 }, //
				{ 13, 1 },//
				{ 15, 16 },
				{ 17, 18 },
				{ 19, 20 },
				{ 15, 20 },
		};
		Arrays.sort(edges, new Comparator<int[]>() {
		    @Override
		    public int compare(int[] o1, int[] o2) {
		        return o1[0] - o2[0];
		    }
		});
		
		List<Tx> txs = new ArrayList<Tx>();
		for (int[] edge : edges) {
			txs.add(new Tx(edge[0], edge[1]));
		}
		HashMap<Integer, List<Tx>> map = new HashMap<Integer, List<Tx>>();

		int group = 0;
		while (!txs.isEmpty()) {// 还有数据
			Tx vertex = txs.get(0);
			Set<Integer> set = new HashSet<Integer>();
			set.add(vertex.getFrom());
			set.add(vertex.getTo());
			Iterator<Tx> iterator = txs.iterator();
			List<Tx> txadd = new ArrayList<Tx>();
			while (iterator.hasNext()) {
				Tx tx = iterator.next();
				if(set.contains(tx.getFrom())||set.contains(tx.getTo())) {
					set.add(tx.getFrom());
					set.add(tx.getTo());
					txadd.add(tx);
					iterator.remove();
				}
			}
			map.put(group, txadd);
			group++;
		}
		map.forEach((key, value) -> {
			System.out.println("group:" + key);
			for (Tx tx : value) {
				System.out.println("\t" + tx);
			}
		});

	}

}
